/**第652题*/
//给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 
//
// 两棵树重复是指它们具有相同的结构以及相同的结点值。 
//
// 示例 1： 
//
//         1
//       / \
//      2   3
//     /   / \
//    4   2   4
//       /
//      4
// 
//
// 下面是两个重复的子树： 
//
//       2
//     /
//    4
// 
//
// 和 
//
//     4
// 
//
// 因此，你需要以列表的形式返回上述重复子树的根结点。 
// Related Topics 树 
// 👍 210 👎 0

package tree.leetcode.editor.cn;

import com.dq.tree.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindDuplicateSubtrees {
    public static void main(String[] args) {
        Solution solution = new FindDuplicateSubtrees().new Solution();
    }
        //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

        List<TreeNode> res = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        findDuplicateSubtrees(root, res, map);
        return res;
    }

    public String findDuplicateSubtrees(TreeNode root, List<TreeNode> res, Map<String,Integer> map) {

        if(root==null) return "#";
        String left = findDuplicateSubtrees(root.left,res,map);
        String right = findDuplicateSubtrees(root.right,res,map);
        //将已经遍历的结构序列化，存储到一个hash表中
        String serial = root.val + "," + left + "," + right;
        if(map.get(serial)==null){
            map.put(serial,1);
        }else{
            map.put(serial,map.get(serial)+1);
        }
        if(map.get(serial)==2){
            res.add(root);
        }
        return serial;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}